package com.yang.Dp.bags;

/**
 * @Author: yang
 * @Description: 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * @Date: Created in 17:24 2022/8/10
 * @Modified By:
 */
public class LeetCode416 {
}

class LeetCode416Solution {
    // 01背包问题 即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包
    // 本题几个关键点 转换为 01背包
    // 背包的体积为sum/2
    // 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
    // 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
    // 背包中每一个元素是不可重复放入。

    // 背包体积为sum/2  对应的就是子集值的二分之一 也就是说我能够找到一个满足sum/2背包的组合 那么我就肯定能够有另外一个子集 那么就满足条件了
    public boolean canPartition(int[] nums) {
        // 1.确定dp[i]含义 对应着下标i的容量我能够得到的最大数值dp[i]
        // 2.确定递推公式 dp[i] = Math.Max(dp[i], (dp[i - nums[i]] + nums[i]))
        // 3.如何初始化？ 从dp[j]的定义来看，首先dp[0]一定是0 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了
        // 如果题目给的价值有负数，那么非0下标就要初始化为负无穷
        // 这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
        // 4.确定遍历顺序 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        // 如果总和是奇数 那么就怎么都不可能平均分配了
        if (sum % 2 == 1) return false;
        sum /= 2;

        int dp[] = new int[sum + 1];
        // java 规范默认数组输出化所有值为0 java.util.Arrays.fill(xx, x)可以将数组初始化为别的元素

        // 外层循环物品
        for(int i = 0; i < nums.length; i++){
            // 内层循环背包容量 且是倒序
            // 背包容量在本题中为nums/2
            for(int j = sum; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[sum] == sum;
    }
}
